/**
 * https://leetcode-cn.com/problems/permutations-ii/
 * 全排列II  给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * @param nums 
 */
const permuteUnique = (nums: number[]): number[][] => {
    const ans: number[][] = []
    const len = nums.length;

    // 存放已经排列了的
    const bols: boolean[] = new Array(len).fill(false)


    // 当前选择的排列
    const cur: number[] = []
    const dfs = (level: number) => {
        if (level > len) {
            ans.push([...cur])
            return
        }
        // [1, 1, 2]
        for (let i = 0; i < len; i++) {
            //! 后面的条件是i前面和自己重复的再选一次
            // 不是第一项并且前一项和自己相同并且没有选, 说明之前哪个已经和我搭配过了
            if (bols[i] || (i > 0 && nums[i] === nums[i - 1] && !bols[i - 1])) continue


            cur.push(nums[i])

            // 标记该项已经选过了
            bols[i] = true

            dfs(level + 1)

            // 恢复
            bols[i] = false
            cur.pop()
        }

    }
    // 排序
    nums.sort((a, b) => a - b)
    dfs(1)
    return ans
};



const permuteUnique2 = (nums: number[]): number[][] => {
    const ans: number[][] = []
    const len = nums.length;

    // 存放已经排列了的
    const bols: boolean[] = []

    /**
     * 判断是否有重复
     * @param arr 
     * @returns 
     */
    const isRepeat = (arr: number[]) => {
        // 判断是否重复, 然后再放入
        for (let i = 0; i < ans.length; i++) {
            if (ans[i].every((a, i) => cur[i] === a)) {
                return true
            }
        }
        return false
    }

    // 当前选择的排列
    const cur: number[] = []
    const dfs = (level: number) => {
        if (level > len) {
            if (!isRepeat(cur)) {
                // 不重复
                ans.push([...cur])
            }
            return
        }

        for (let i = 0; i < len; i++) {
            if (!bols[i]) {
                cur.push(nums[i])

                // 标记该项已经选过了
                bols[i] = true

                dfs(level + 1)

                // 恢复工作
                bols[i] = false
                cur.pop()
            }
        }

    }

    dfs(1)
    return ans
};

console.log(permuteUnique([1, 1, 2]))